/**
 * @author Michael Robinette
 * A10243792
 * cs12vbl
**/
import java.util.*;

public class DoublyLinkedList12 implements List12
{
  private Node _firstNode = null;
  private Node _lastNode = null;
  private int _numElements = 0;

  public DoublyLinkedList12() { }
 
  /** Adds the specified Object <tt>o</tt>, which may be null, to the
    * front of the list (i.e., at the head).
    * @param o the object to add to the list. */
  public void addToFront (Object o)
  {
    if (_firstNode == null)
      _firstNode = _lastNode = new Node(o);
    else
    {
      // Make a new node with the given data and pointing to the current first
      Node newNode = new Node(o, null, _firstNode);

      // Set the current first's last node to the new node
      _firstNode.__last = newNode;
      _firstNode = newNode; // Make our new node the first
    }

    _numElements++;
  }
  
  /** Adds the specified Object <tt>o</tt>, which may be null, to the
    * back of the list (i.e., at the tail).
    * @param o the object to add to the list. */
  public void addToBack(Object o)
  {
    // First check if there is already a list, or if this is the first link
    // Check by seeing if _firstNode is pointing to anything
    if (_firstNode == null)
    {
      // Throw it into the _firstNode handle
      _firstNode = _lastNode = new Node(o); 
    }
    else
    {
      // There is already a list, add it after the last node
      Node node = new Node(o, _lastNode); // Make the new node
      _lastNode.__next = node; // Set the next node for the current last node
      _lastNode = node; // Set the _lastNode to be our new node
    }

    // Make sure to increment to show the size increase
    _numElements++;
  }
  
  /** Equivalent to addToBack.
    * @param o the object to add to the list. */
  public void add (Object o)
  {
    addToBack(o); // Just use addToBack
  }

  /** Removes and returns the element at the front of the list.
    * @return the element that was removed from the front of the list.
    * @throws NoSuchElementException if the list was empty.
    */
  public Object removeFront () throws NoSuchElementException
  {
    // First check that the _firstNode is not null as that means there is no list
    if (_firstNode == null)
      throw new NoSuchElementException();

    // Get the first node
    Node rm = _firstNode;

    if (_firstNode == _lastNode)
    {
      // Compare their addresses to see if they are pointing to the same object
      _firstNode = _lastNode = null; // Set them both to null
      _numElements = 0; // Set the size to 0
    }
    else
    {
      // Only do this step if the next node is non-null
      if (rm.__next != null)
      {
        // Set the next node in the links last node to null, as it is gone
        rm.__next.__last = null;
      }

      // Set the first node to the old firsts next
      _firstNode = rm.__next;

      // Decrement the size
      _numElements--;
    }

    // Return the old nodes data
    return rm.__data;
  }

  /** Removes and returns the element at the back of the list.
    * @return the element that was removed from the back of the list.
    * @throws NoSuchElementException if the list was empty.
    */
  public Object removeBack () throws NoSuchElementException
  {
    // Check that there is a list
    if (_lastNode == null)
      throw new NoSuchElementException();

    // Point our remove node to the _lastNode
    Node rm = _lastNode;

    // Check if their addresses are the same
    if (_firstNode == _lastNode)
    {
      // Same addresses, empty the list
      _firstNode = _lastNode = null;
      _numElements = 0;
    }
    else
    {
      if (rm.__last != null)
      {
        // Set the last nodes next reference to null
        rm.__last.__next = null;
      }

      // Set the last node to the node before the last
      _lastNode = rm.__last;

      // Make sure we decrement to reflect new size
      _numElements--;
    }

    return rm.__data; // Return the data for the deleted node
  }

  /** Removes the first occurrence (ordered from front to
   * back, i.e., head to tail of the list) of the specified
   * Object <tt>o</tt> from the list, if it exists. <tt>o</tt> may be null; if
   * it is, then this method removes the first element in
   * the list that is null. Otherwise, this method removes
   * the first element in the list that <tt>equals()</tt>
   * <tt>o</tt> (if any such element exists).
   * @return <tt>true</tt> if an element was removed, or
   * <tt>false</tt> otherwise.
   */
  public boolean remove (Object o)
  {
    Node rm = _firstNode; // Holds the node we are going to remove
    boolean found = false; // If this changes to true then the correct value was found

    // Check that the first rm is not null. 
    // If it is then return false, as there is no list
    if ( rm == null)
      return false;

    // Keep going while the next node is non-null
    while (rm != null)
    {
      if (rm.__data == o)
      {
        found = true;
        break;
      }
      else if (rm.__data.equals(o))
      {
        found = true;
        break;
      }  

      rm = rm.__next;
    }

    /*Check to see if rm is the first or last node. If it is not then we
      set the nodes last and next to the correct variables. We do this
      check so that if you are removing the first or last node in the
      list you will not throw a null pointer exception.*/
    if (found)
    {
      if (rm.__last != null)
        rm.__last.__next = rm.__next;
      else
        _firstNode = rm.__next;

      if (rm.__next != null)
        rm.__next.__last = rm.__last;
      else
        _lastNode = rm.__last;

      _numElements--;

      return true;
    }

    return false; 
  }

  /** Removes all elements from the list. */
  public void clear ()
  {
    // All we have to do is point the first and last node to null and the link
    // will be broken
    _firstNode = _lastNode = null;
    _numElements = 0; // Make sure to set the size to 0
  }

  /** Returns the element stored at location <tt>index</tt>, where index 0
   * is the element stored at the head of the list and <tt>size()-1</tt> is
   * the index of the element at the tail of the list.
   * @param index the index of the element to retrieve.
   * @throws IndexOutOfBoundsException if the index is invalid.
   * @return the Object at the specified index.
   */
  public Object get (int index) throws IndexOutOfBoundsException
  {
    // Bounds check it.
    // Null check on _firstNode is redundent, but is just for safety
    if (index >= _numElements || index < 0 || _firstNode == null)
      throw new IndexOutOfBoundsException();

    // Check for which end is closer to save some time
    if (index <= _numElements / 2)
    {
      // Search from front to back
      Node node = _firstNode;
      for (int i = 0; i <= index; i++)
      {
        if (i == index)
          return node.__data;
        else
          node = node.__next;
      }
    }
    else
    {
      // Search from back to front
      Node node = _lastNode;
      for (int i = _numElements - 1; i >= index; i--)
      {
        if (i == index)
          return node.__data;
        else
          node = node.__last;
      }
    }

    // Didn't find it, so just return null
    return null;
  }

  /** Returns the number of elements (null or otherwise) currently stored in the
   * list.
   * @return the number of elements stored in the list.
   */
  public int size ()
  {
    return _numElements;
  }

  /** Returns whether the specified Object <tt>o</tt> is contained in the list. <tt>o</tt>
   * may be null.
   * @param o the object whose presence in the list should be determined.
   * @return whether <tt>o</tt> is contained in the list.
   */
  public boolean contains (Object o) 
  {
    // Searching from front to back
    Node node = _firstNode;

    // Loop while the node is non null
    while (node != null)
    {
      // Check the references for null
      if (node.__data == o)
      {
        return true;
      }
      else if (node.__data.equals(o))
      {
        return true;
      }

      // Go to the next node
      node = node.__next;
    }

    // Not found by now so return false
    return false;
  }

  // Iterator for the iterable interface
  public Iterator iterator()
  {
    return new ListIter(); // Return a new ListIter
  }

  // ListIter inner class
  class ListIter implements Iterator
  {
    // _current holds the current node. Like a cursor
    Node __cursor;
    boolean _removed = false;

    public boolean hasNext()
    {
      // Check if current is null, this means next has not been called yet
      if (_current == null)
      {
        // Return the test that there is at least one node ie the first
        return (_firstNode != null);
      }
      else
      {
        // Cursor is not null so return if its next is null
        return (_current.__next != null);
      }
    }

    public void remove() throws IllegalStateException
    {
      if (_removed)
      {
	throw new IllegalStateException();
      }

      // If the _current is null then next has never been called
      if (_current == null)
	throw new IllegalStateException();

      if (_current.__last != null)
	_current.__last.__next = _current.__next;
      else
	_firstNode = _current.__next;

      if (_current.__next != null)
	_current.__next.__last = _current.__last;
      else
	_lastNode = _current.__last;

      // Point the current to the currents last
      _current = _current.__last;

      _numElements--;
      _removed = true;
    }

    public Object next() throws NoSuchElementException
    {
      // Check to make sure the _current is pointing to a valid node
      if (_current == null)
      {
	// Not pointing to a valid node, first time being called
	// Set the _current to the lists _firstNode and return the data
	_current = _firstNode;
	_removed = false;
	return _current.__data;
      }
      else
      {
	// Already pointing to a valid node, check if its next is non-null
	if (_current.__next == null)
	  throw new NoSuchElementException(); // Next is null, throw exception

	// The next is alright so point to it and return the data
	_current = _current.__next;
	_removed = false;
	return _current.__data;
      }
    }
  }

  class Node
  {
    Object __data; // Holds the actual data stored in the node
    Node __next, __last; // __next is a reference to the next node, __last is last

    /**
     * Don't need to do anything for a no-arg, Just make a dummy (null all)
     **/
    public Node() { }

    /**
     * Single-arg ctor that takes the data to store, __next and __last are null
     **/
    public Node(Object data)
    {
      __data = data; // Store the data
    }

    /**
     * Two arg that takes the data and the last node reference
     **/
    public Node(Object data, Node last)
    {
      __data = data; // Store the data
      __last = last; // Store the last reference
    }

    /**
     * Three-arg ctor that takes the data to store, a reference to the last
     * node, and a reference to the next node
     **/
    public Node(Object data, Node last, Node next)
    {
      __data = data;
      __last = last;
      __next = next;
    }
  }
}

